package basic.study.leetcode;

/**
 * @author Kevin
 * @date 2020/2/25 15:42
 * 169 求众数
 * 最常见就是哈希解决
 * 使用分治思想解决
 */
public class Easy169 {
    public static void main(String[] args) {
        int[] input = {3,2,3};
        System.out.println(solution(input, 0, input.length-1));
    }
    //返回值为众数
    public static int solution(int[] nums, int lo, int hi) {
        //结束分治条件
        if (lo == hi) return nums[lo];

        int mid = lo + (hi - lo) >> 1;
        int left = solution(nums, lo, mid);
        int right = solution(nums, mid+1, hi);
        //如果两边众数相同
        if (left == right) {
            return left;
        } else { //如果两边众数不同
            int leftCount = countInRange(nums, left, lo, mid);
            int rightCount = countInRange(nums, right, mid+1, hi);
            return leftCount > rightCount ?left:right;
        }

    }
    public static int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i < hi; i++) {
            if (nums[i] == num) {
                count ++;
            }
        }
        return count;
    }


}
